package zhanyuduilie

func IsValid(s string) bool {
	// 找到第一个反向的元素，从改位置开始反向比较，直至比完，然后接着比
	correct := map[uint8]uint8{'(': ')', '[': ']', '{': '}'}
	if len(s)%2 != 0 {
		return false
	}
	stack := make([]uint8, 0)

	for i := 0; i < len(s); i++ {
		if _, ok := correct[s[i]]; ok {
			// 左边元素
			stack = append(stack, s[i])
		} else {
			// 右边元素
			if len(stack) == 0 {
				return false
			}
			if correct[stack[len(stack)-1]] != s[i] {
				return false
			} else {
				stack = stack[:len(stack)-1]
			}
		}
	}
	if len(stack) == 0 {
		return true
	}
	return false
}
